package Aula15;

public class ArvoreBinariaImpl implements ArvoreBinaria {

	private No raiz;
	private String ordem;

	public ArvoreBinariaImpl() {
		super();
	}

	private int[] strToNumeros(String str) {
		String[] array = str.split(" ");
		int[] numeros = new int[array.length];
		for (int i = 0; i < array.length; i++) {
			try{
				numeros[i] = Integer.parseInt(array[i]);
			}catch(NumberFormatException e){
				throw new ArvoreBinariaException("Arvore so permite inteiros");
			}
		}
		return numeros;
	}
	
	private void emOrdem(No n){
		
		if (n != null) {
		     emOrdem(n.left);
		     if(n.left != null){
		    	 ordem += " ";
		     }
		     ordem += n.key;
		     if(n.right != null){
		    	 ordem += " ";
		     }
		     emOrdem(n.right);
		}
	}

	public String imprimeEmOrdem() {
		ordem = "";
		emOrdem(raiz);
		return ordem;
	}

	public void insere(String s) {
		int[] numeros = strToNumeros(s);
		for (int i = 0; i < numeros.length; i++) {

			No novoNo = new No(numeros[i]);
			No pai = null;
			No no = raiz;

			while (no != null) {
				pai = no;
				if (no.key >= novoNo.key) {
					no = no.left;
				}else {
					no = no.right;
				}
			}
			novoNo.parent = pai;			
			
			if(pai == null){
				raiz = novoNo;
			}
			else if (pai.key >= novoNo.key) {
				pai.left = novoNo;
			} else {
				pai.right = novoNo;
			}
		}
	}
	
	private No sucessor(No n){
		if(raiz == null){
			throw new ArvoreBinariaException("Arvore nao iniciada!");
		}
		No proximo = n.parent;
		if(n.right != null){
			proximo = n.right;
			while(proximo.left != null){
				proximo = proximo.left;
			}
		}
		return proximo;
	}
	
	private void removeNo(No n){
		No y, x;
		if(n.left == null || n.right == null){
			y = n;
		}else{
			y = sucessor(n);
		}
		if(y.left != null){
			x = y.left;
		}else{
			x = y.right;
		}
		if(x != null){
			x.parent = y.parent;
		}
		if(y.parent == null){
			raiz = x;
		}else if(y.key == y.parent.left.key){
			y.parent.left = x;
		}else{
			y.parent.right = x;
		}
		if(y.key != n.key){
			n.key = y.key;
		}
	}
	
	private No getNo(int key){
		No no = raiz;
		if(no == null){
			throw new ArvoreBinariaException("Arvore nao iniciada.");
		}
		while(no.key != key){
			if(key > no.key){
				if(no.right != null){
					no = no.right;
				}else{
					return null;
				}
			}else{
				if(no.left != null){
					no = no.left;
				}else{
					return null;
				}
			}
		}
		return no;
	}

	public void remove(String s) {
		int[] numeros = strToNumeros(s);
		No no;
		for(int i = 0; i < numeros.length; i++){
			no = getNo(numeros[i]);
			if(no != null){
				removeNo(no);
			}
		}
	}
	
	public static void main(String[] args) {
	    
        ArvoreBinaria arvore = new ArvoreBinariaImpl();
        ArvoreBinaria arvore2 = new ArvoreBinariaImpl();
               
        arvore.insere("10 9 8 7 6 5 4 3 2 1");
        System.out.println(arvore.imprimeEmOrdem());

        arvore.remove("10 8 6 2 1");

        System.out.println(arvore.imprimeEmOrdem());


        arvore2.insere("10 15 2 3 4 5");

        System.out.println(arvore2.imprimeEmOrdem());

        arvore2.remove("2 10 15");

        System.out.println(arvore2.imprimeEmOrdem());

            
    }

}
